package com.learning.datastruct.tree;

import java.util.Comparator;

/**
 * @author ADMIN
 * @Classname BalancedBinarySearchTree
 * @date 2022/2/8 7:17
 */
public class BalancedBinarySearchTree<E> extends BinarySearchTree<E> {
    public BalancedBinarySearchTree() {
        super();
    }

    public BalancedBinarySearchTree(Comparator<E> comparator) {
        super(comparator);
    }
    /**
     *      对节点y进行向左旋转操作，返回旋转后新的根节点x
     *         g                             p
     *       /  \                          /   \
     *      T1   p      向左旋转 (g)       g     n
     *          / \   - - - - - - - ->   / \   / \
     *        T2  n                     T1 T2 T3 T4
     *           / \
     *         T3 T4
     */
    protected void rotateLeft(Node<E> grand) {
        Node<E> parent =  grand.right;
        Node<E> child =  parent.left;
        grand.right = child;
        parent.left = grand;
        afterRotate(grand, parent, child);
    }

    /**
     * 对节点y进行向右旋转操作，返回旋转后新的根节点x
     *        g                               p
     *       / \                            /   \
     *      p   T4     向右旋转 (g)         n     g
     *     / \       - - - - - - - ->    / \   / \
     *    n   T3                       T1  T2 T3 T4
     *   / \
     * T1   T2
     **/
    protected void rotateRight(Node<E> grand) {
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;
        afterRotate(grand, parent, child);
    }
    protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else {
            root = parent;
        }
        if (child != null) {
            child.parent = grand;
        }
        grand.parent = parent;
    }
}
